package l.l.w.CodingInterviews;

/**
 * Created by llw on 2018/4/1/0001.
 */
public class 数组中的逆序对 {
    public static void main(String[] args) {
        int [] array = {364,637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,174,557,67,746,550,474,162,268,142,463,221,882,576,604,739,288,569,256,936,275,401,497,82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,433,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575};
        int i = new 数组中的逆序对().InversePairs(array);
        if(i > 1000000007 )
            i = i % 1000000007;
        System.out.println(i);
        System.out.println(496758197 % 1000000007);
    }
    public int InversePairs(int [] array) {
        int nums = 0;
        if(array == null || array.length == 0) return nums;
        int start = 0,end = array.length-1;
        nums = mergeSort(array,start,end,nums);
        return nums;
    }
    private int mergeSort(int[] array,int start,int end, int nums){
        if(start >= end) return nums;
        if(start + 1 == end){
            if(array[start] > array[end]){
                nums++;
                swap(array,start,end);
            }
            return nums;
        }
        int mid = (start+end)/2;
        nums = mergeSort(array,start,mid,nums);
        if(nums >= 1000000007 ) nums = nums % 1000000007;
        nums = mergeSort(array,mid+1,end,nums);
        if(nums >= 1000000007 ) nums = nums % 1000000007;
        int i = start,j=mid+1;
        int[] temp = new int[end - start + 1];
        int k = 0;
        long c = 0;
        while(i <= mid && j <= end){
            if(array[i] <= array[j]){
                temp[k++] = array[i++];
            }else{
                temp[k++] = array[j++];
                c += mid - i+1;
            }
        }
        if(c > 1000000007) c= c % 1000000007;
        nums += c;
        while(i <= mid){
            temp[k++] = array[i++];
        }
        while(j <= end){
            temp[k++] = array[j++];
        }
        for(i = start,k = 0; i <= end;++i,k++ ){
            array[i] = temp[k];
        }
        return nums;
    }
    private void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
